package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 691. 贴纸拼词    https://leetcode.cn/problems/stickers-to-spell-word/
 */
public class LeetCode691 {

    // 1、超时，暴力递归
    public static int minStickers1(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target.length() == 0) {
            return -1;
        }
        int ans = process(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private static int process(String[] stickers, String rest) {
        if (rest.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String sticker : stickers) {
            String sub = subString(sticker, rest);
            if (rest.length() != sub.length()) {
                min = Math.min(min, process(stickers, sub));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    private static String subString(String sticker, String rest) {
        int[] s = new int[26];
        char[] stickerChar = sticker.toCharArray();
        char[] restChar = rest.toCharArray();
        for (char c : restChar) {
            s[c - 'a']++;
        }
        for (char c : stickerChar) {
            s[c - 'a']--;
        }
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < s.length; i++) {
            if (s[i] > 0) {
                for (int j = 0; j < s[i]; j++) {
                    char append = (char) ('a' + i);
                    sb.append(append);
                }
            }
        }
        return sb.toString();
    }

//    // 2、增加分叉
//    public static int minStickers2(String[] stickers, String target) {
//        if (stickers == null || stickers.length == 0 || target.length() == 0) {
//            return -1;
//        }
//        int[][] stickersCount = new int[stickers.length][26];
//        for (int i = 0; i < stickersCount.length; i++) {
//            for (char c : stickers[i].toCharArray()) {
//                stickersCount[i][c - 'a']++;
//            }
//        }
//        int ans = process2(stickersCount, target);
//        return ans == Integer.MAX_VALUE ? -1 : ans;
//    }
//
//    private static int process2(int[][] stickersCount, String rest) {
//        if (rest.length() == 0) {
//            return 0;
//        }
//        int min = Integer.MAX_VALUE;
//        for (int i = 0; i < stickersCount.length; i++) {
//            // 作了第一个字母包含过滤分支
//            if (stickersCount[i][rest.charAt(0) - 'a'] > 0) {
//                // rest次数统计
//                int[] restCount = new int[26];
//                char[] chars = rest.toCharArray();
//                for (int j = 0; j < rest.length(); j++) {
//                    restCount[chars[j] - 'a']++;
//                }
//                // sub操作
//                StringBuilder sb = new StringBuilder("");
//                for (int j = 0; j < 26; j++) {
//                    restCount[j] = restCount[j] - stickersCount[i][j];
//                    if (restCount[j] > 0) {
//                        for (int k = 0; k < restCount[j]; k++) {
//                            sb.append((char) (j + 'a'));
//                        }
//                    }
//                }
//                min = Math.min(min, process2(stickersCount, sb.toString()));
//            }
//        }
//        return min + (min == Integer.MAX_VALUE ? 0 : 1);
//    }

    // 3、增加缓存
    public static int minStickers3(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target.length() == 0) {
            return -1;
        }
        int[][] stickersCount = new int[stickers.length][26];
        for (int i = 0; i < stickersCount.length; i++) {
            for (char c : stickers[i].toCharArray()) {
                stickersCount[i][c - 'a']++;
            }
        }
        Map<String, Integer> map = new HashMap<>();
        int ans = process2(stickersCount, target, map);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private static int process2(int[][] stickersCount, String rest, Map<String, Integer> map) {
        if (map.containsKey(rest)) {
            return map.get(rest);
        }
        if (rest.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < stickersCount.length; i++) {
            // 作了第一个字母包含过滤分支
            if (stickersCount[i][rest.charAt(0) - 'a'] > 0) {
                // rest次数统计
                int[] restCount = new int[26];
                char[] chars = rest.toCharArray();
                for (int j = 0; j < rest.length(); j++) {
                    restCount[chars[j] - 'a']++;
                }
                // sub操作
                StringBuilder sb = new StringBuilder("");
                for (int j = 0; j < 26; j++) {
                    restCount[j] = restCount[j] - stickersCount[i][j];
                    if (restCount[j] > 0) {
                        for (int k = 0; k < restCount[j]; k++) {
                            sb.append((char) (j + 'a'));
                        }
                    }
                }
                min = Math.min(min, process2(stickersCount, sb.toString(), map));
            }
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        map.put(rest, ans);
        return ans;
    }

    public static void main(String[] args) {
        String[] stickers1 = {"with", "example", "science"};
        String target1 = "thehat";
        System.out.println(minStickers3(stickers1, target1));  // 3

        String[] stickers2 = {"control", "heart", "interest", "stream", "sentence", "soil", "wonder", "them", "month", "slip", "table", "miss", "boat", "speak", "figure", "no", "perhaps", "twenty", "throw", "rich", "capital", "save", "method", "store", "meant", "life", "oil", "string", "song", "food", "am", "who", "fat", "if", "put", "path", "come", "grow", "box", "great", "word", "object", "stead", "common", "fresh", "the", "operate", "where", "road", "mean"};
        System.out.println(minStickers3(stickers2, "stoodcrease"));  // -1

        String[] stickers3 = {"heavy","claim","seven","set","had","it","dead","jump","design","question","sugar","dress","any","special","ground","huge","use","busy","prove","there","lone","window","trip","also","hot","choose","tie","several","be","that","corn","after","excite","insect","cat","cook","glad","like","wont","gray","especially","level","when","cover","ocean","try","clean","property","root","wing"};
        System.out.println(minStickers3(stickers3, "travelbell"));  // 3
    }

}
